// @algorithm @lc id=347 lang=cpp 
// @title top-k-frequent-elements


// @test([1,1,1,2,2,3],2)=[1,2]
// @test([1],1)=[1]
using T = pair<int,int>;
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> freq;
        for(auto & n : nums)
            freq[n]++;

        auto cmp = [](const T & a, const T & b){
            return a.second > b.second;
        };
        priority_queue<T, vector<T>, decltype(cmp)> heap(cmp);
        for(auto & p : freq){
            if(heap.size()==k){
                if(heap.top().second >= p.second)
                    continue;
                heap.pop();
            }
            heap.push(p);
        }

        vector<int> ans;
        while(heap.size()){
            ans.push_back(heap.top().first);
            heap.pop();
        }
        return ans;
    }
};